package LeetCode;

import java.util.HashMap;

/**
 * @Author: Dijah
 * @Date: 2023/1/13 14:08
 * @Desc: 给定一个前序遍历和后续遍历，构建一个树
 *
 */
public class code889_constructFromPrePost {

     public static class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
     }

    static HashMap<Integer,Integer> map = new HashMap<>();

    public static TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        if(preorder == null){
            return null;
        }
        for(int i = 0; i < postorder.length; i++){
            map.put(postorder[i],i);
        }
        return build(preorder,0,preorder.length - 1,
                postorder,0,postorder.length - 1);
    }

    public static TreeNode build(int[] preorder,int preStart,int preEnd,int[] postorder,int postStart,int postEnd){

        if(preStart > preEnd){
            return null;
        }
        //当没有子节点的时候两者是相等的
        if(preStart == preEnd){
            return new TreeNode(preorder[preStart]);
        }
        //在前序遍历中第一个值一定是头
        //前序 头的位置


        int leftRootVal = preorder[preStart + 1];
        //在后续遍历（postStart）中 头 节点位置的 index
        int index = map.get(leftRootVal);
        // leftSize 的值计算
        int leftSize = index - postStart + 1;
        int headVal = preorder[preStart];
        TreeNode head = new TreeNode(headVal);
        //左子树是preorder 的 presStart + 1 位置的值

        //构建左子树
        head.left = build(preorder,preStart + 1,preStart + leftSize,
                postorder,postStart,index);
        //构建右子树
        head.right = build(preorder,preStart + leftSize + 1,preEnd,
                postorder,index + 1,postEnd - 1);
        return head;
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new  TreeNode(2);
        TreeNode node3 = new  TreeNode(3);
        TreeNode node4 = new  TreeNode(4);
        TreeNode node5 = new  TreeNode(5);
        TreeNode node6 = new  TreeNode(6);
        TreeNode node7 = new  TreeNode(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        int [] preorder = {1,2,4,5,3,6,7};
        int [] postorder = {4,5,2,6,7,3,1};
        TreeNode treeNode = constructFromPrePost(preorder, postorder);
        System.out.println(treeNode.val);
    }
}
